// https://leetcode.cn/problems/minimum-genetic-mutation/description/?envType=study-plan-v2&envId=top-interview-150

class Solution {
private:
    bool isNeighbor(string a, string b) {
        int n = a.size();
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] != b[i]) {
                count++;
            }
        }
        return count == 1;
    }

public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        int n = bank.size();
        
        if (n == 0) {
            return -1;
        }

        unordered_map<string, bool> visited;
        for (int i = 0; i < n; i++) {
            visited[bank[i]] = false;
        }
        queue<pair<string, int>> q;
        q.push({startGene, 0});

        while (!q.empty()) {
            auto top = q.front();
            q.pop();

            for (int i = 0; i < n; i++) {
                if (!visited[bank[i]] && isNeighbor(top.first, bank[i])) {
                    if (bank[i] == endGene) {
                        return top.second + 1;
                    }
                    visited[bank[i]] = true;
                    q.push({bank[i], top.second + 1});
                }
            }
        }

        return -1;
    }
};